package Stack;

import java.util.*;

/**
 *  题目 ：使用栈操作来构建数组
 *  题目详述 ：
 *  给你一个数组 target 和一个整数 n。每次迭代，需要从list = { 1 , 2 , 3 ..., n } 中依次读取一个数字。
 *
 * 请使用下述操作来构建目标数组 target ：
 *
 * "Push"：从 list 中读取一个新元素， 并将其推入数组中。
 * "Pop"：删除数组中的最后一个元素。
 * 如果目标数组构建完成，就停止读取更多元素。
 * 题目数据保证目标数组严格递增，并且只包含 1 到 n 之间的数字。
 *
 * 请返回构建目标数组所用的操作序列。如果存在多个可行方案，返回任一即可。
 *
 */
public class StackToArray {
//    List<String> stack;
//    public List<String> buildArray(int[] target, int n) {
        /**
         *  核心思想 ：（只是需要用栈操作构建target数组，并不是使用栈的数据结构）
         *  方法一 ：（通过遍历1 ~ n元素，与target数组中元素进行比较）
         *  即，遍历1 ~ n的同时，与target数组中的元素进行比较；
         *  步骤 ：
         *  （1）在遍历1 ~ n时，每次先将push插入list链表中；
         *  （2）当n和target数组中的元素不一致时，需要将其弹出pop，同时不需要进行j++;
         *  （3）若是n和target数组中的元素一致时，需要进行j++;
         *  （4）判断target数组是否遍历结束（ 若是j == target.length，即等价于已经遍历完target数组中的所有元素）
         */
//        stack = new ArrayList<>();
//        int j = 0;
//        for(int i = 1 ; i <= n ; i++){
//            stack.add("Push");
//            System.out.println(i);
//            System.out.println(j);
//            // 当n和target数组中的元素不一致时，需要将其弹出，同时不需要进行j++;
//            if(target[j] != i){
//                stack.add("Pop");
//                continue;
//            }
//            // 若是n和target数组中的元素一致时，需要进行j++;
//            j++;
//            // 若是j == target.length，即等价于已经遍历完target数组中的所有元素
//            if (j == target.length){
//                break;
//            }
//        }
//        return stack;
//    }

    public List<String> buildArray(int[] target, int n) {
        /**
         *  方法二 ：（通过遍历target数组，在 1 ~ n的范围内进行查找
         *
         */
        List<String> res = new ArrayList<String>();
        int prev = 0; //
        for (int number : target) { // 遍历target数组中每一个元素
            for (int i = 0; i < number - prev - 1; i++) {
                // 在target数组中元素number之前的元素，都需要 栈操作"push"和"pop"
                res.add("Push");
                res.add("Pop");
            }
            res.add("Push");
            // 使得prev = number，即等于target数组中的第一个数组元素（由于target数组元素是递增的）
            prev = number;
        }
        return res;
    }
}
